#include <bits/stdc++.h>

using namespace std;

// 给你一棵以root为根的二叉树、一个以head为头的链表
// 在二叉树中，有很多一直向下的路径
// 如果某个路径上的数值等于以head为头的整个链表
// 返回True，否则返回False
// 测试链接 : https://leetcode.cn/problems/linked-list-in-binary-tree/

// 不要提交这个类
struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 不要提交这个类
struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution 
{
public:
    int s2[101];
    int next[101];
    int m = 0;

    bool isSubPath(ListNode* head, TreeNode* root) 
    {
        while(head)
        {
            s2[m++] = head->val;
            head = head->next;
        }
        nextArray();
        return find(root, 0);
    }

	// 二叉树来到cur节点了
	// 链表比对的位置来到i位置
	// 利用链表的next数组加速匹配
	// 返回是否能把链表整体匹配出来
    bool find(TreeNode* cur, int i)
    {
        if(i == m) return true;
        if(cur == nullptr) return false;
		// 当前来到cur节点, 一开始的i是父亲节点给的
		// 但是要修正，找到配成的位置
		// 均摊下来，时间复杂度O(1)
        while(i >= 0 && cur->val != s2[i])
        {
            i = next[i];
        }
        return find(cur->left, i + 1) || find(cur->right, i + 1);
    }

    void nextArray()
    {
        if(m == 1)
        {
            next[0] = -1;
            return;
        }
        next[0] = -1, next[1] = 0;
        int i = 2, cn = 0;
        while(i < m)
        {
            if(s2[i - 1] == s2[cn])
                next[i++] = ++cn;
            else if(cn > 0)
                cn = next[cn];
            else
                next[i++] = 0;
        }
    }
};


class Solution 
{
public:
    bool isSubPath(ListNode* head, TreeNode* root) 
    {
        if(head == nullptr) return true;
        if(root == nullptr) return false;
        return f(head, root)
            || isSubPath(head, root->left)
            || isSubPath(head, root->right);
    }

    bool f(ListNode* head, TreeNode* root)
    {
        if(head == nullptr) return true;
        if(root == nullptr) return false;
        if(head->val != root->val) return false;
        return f(head->next, root->left)
            || f(head->next, root->right);
    }
};